package com.c2b.algorithm.newcoder.dynamic_programming;

/**
 * <a href="https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj">跳台阶</a>
 * <p>一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。</p>
 * 数据范围：1≤n≤40<br>
 * 要求：时间复杂度：O(n) ，空间复杂度：O(1)<br>
 *
 * @author c2b
 * @since 2023/3/15 10:29
 */
public class BM0063JumpFloor_S {
    /**
     * 动态规划
     */
    public int jumpFloor(int target) {
        if (target <= 2) {
            return target;
        }
        // 初始化变量：f(1)=1、f(2)=2
        int a = 1;
        int b = 2;
        int res = 0;
        for (int i = 3; i <= target; i++) {
            res = a + b;
            a = b;
            b = res;
        }
        return res;
    }

    public int jumpFloor_Recursion(int target) {
        if (target <= 2) {
            return target;
        }
        return jumpFloor_Recursion(target - 1) + jumpFloor_Recursion(target - 2);
    }

    public static void main(String[] args) {
        BM0063JumpFloor_S bm0063JumpFloor_s = new BM0063JumpFloor_S();
        System.out.println(bm0063JumpFloor_s.jumpFloor(7));
        System.out.println(bm0063JumpFloor_s.jumpFloor_Recursion(7));
    }
}
